package com.leetcode.algorithm.y22.m06;

/**
 * 740. 删除并获得点数
 * 
 * https://leetcode.cn/problems/delete-and-earn/
 * 
 * @author jie.deng
 *
 */
class Question0740Solution01 {

	public int deleteAndEarn(int[] nums) {
		// 1 <= nums.length <= 2 * 10000
		// 1 <= nums[i] <= 10000
		int maxNum = nums[0];
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] > maxNum) {
				maxNum = nums[i];
			}
		}

		int[] seqNums = new int[maxNum + 1];
		for (int i = 0; i < nums.length; i++) {
			seqNums[nums[i]] += nums[i];
		}

		int[][] dp = new int[maxNum + 1][2];
		dp[0][0] = 0;
		dp[0][1] = seqNums[0];

		for (int i = 1; i < maxNum + 1; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
			dp[i][1] = seqNums[i] + dp[i - 1][0];

		}
		return Math.max(dp[maxNum][0], dp[maxNum][1]);
	}

}